众所周知,abc题解不会有abc的
本场链接:https://atcoder.jp/contests/abc173
不会还是提一下C,C实际上只是一个爆搜,但是没必要修改棋盘状态,标记某一列某一行有没有被覆盖再统计就可以了,一共四种修改方案直接写dfs就好。
D:
题目大意:有个人,每个人有一个友好值,每个人进入的时候,会获得坐的位置两边的两个人的友好值中较小的舒适值,并且所有人会坐成一个环。第一个人没有舒适值,并且新来的位置可以插入到环中,问最后能获得多大的舒适值总和。
注意每个人进来的顺序不是固定的,并且位置可以插入原有的两个人之间。
题目范围:
分析
注意到每个人来的顺序不是固定的,而且第一个人是拿不到舒适值的,可以想到第一个人一定是最大的人,因为假如第二个人较小则获得的收益降低,若相同则不影响,结果不会变差。
其次可以拓展出整个过程肯定也是先选大的进去比较好,所以整个序列的编排顺序应该是从大到小依次插入的。每次应该选择整个序列中次大的值。由于可以插入到任意位置之间,这导致一个人实际上可以用两次,因为这个人会有两个相邻的人在,就可以放在两边算两次了(可以画图辅助理解一下)。
因此我们维护一个优先队列即可:第一权值是本身的值,第二权值是当前使用过的次数,假如次数是的话,那么还可以入队一起,否则就直接不管,踢出队列不加回来。每次对新的查询次大值即可。
到这里实际上还不能完整做完本题。首先对于第二个人来说它来检测的时候肯定就没有次大值,这个时候可能就要特判掉他(之前就加入)这个时候就有一个坑点了,最大值的那个人次数不能是而应该是,因为这个最大值是被第二个人用过的,如果不加会掉两个点。最后记得开LL就行。
代码
[D solution]: https://atcoder.jp/contests/abc173/submissions/15010878E:
题目大意:给个数的一个数列,从中选出个数,使总乘积最大。结果对取余。
数据范围:
(本题有网上原题)
分析
首先肯定是排个序,完了之后肯定要从两边去选(存在负数的问题)。可以发现,由于负数是两两选择的,我们也同样可以在正数的选择策略上选择同样的方式。即排序之后从两边两两选择。
假如说是个奇数,首先削掉,最大的肯定要选进去。假如说最大的都是负数,则后面的肯定也要选一个负数乘积出来,特殊标记一下。
之后两两选数,从起点和末尾分别开始,选两边较大的一对数加入答案,由于说有上面的特殊标记的问题,所以两边算出来的乘积需要再乘上特殊标记,因为在有标记的时候是要找出负数最小的乘积,反之则是最大的。注意一下就行。正确性比较显然,削掉奇数的情况之后两两选择也肯定能选完。
不过本题还涉及到负数取余的问题,注意在最后把取余调回正数就可以了。
代码
[E solution]: https://atcoder.jp/contests/abc173/submissions/15015304F:
题目大意:给定一颗节点的树,定义函数为把树上所有编号在之间的留下,并保留他们之间的边,剩余的联通块的数量。最终答案为
数据范围:
(本题也有原题,只不过是另外一题是完整的链,这题是个树,但不影响)
另外一题链接:https://codeforces.com/contest/1151/problem/E
那一场的题解:
分析
这个式子想拆看着也很难拆,又是两个求和,考虑算单个贡献。
第一个比较容易想到的结论就是:联通块的数量=点数 - 边数。由于范围特别大,只能说遍历一下每个点,于是顺理成章的我们来考虑单个点对整个答案的贡献是怎样的。
首先对于点数,假如说产生了贡献,那么他对某个产生了贡献的区间满足,进而可以算出对于单个点来说他一共会对点数产生的贡献。
其次对于边数,假如说当前的边连接的两个分别是和,那么这个边产生贡献,当且仅当和都产生了贡献时,也就是说他俩都被算进图里的时候才会有贡献。那么下界肯定是较小者,上界是较大者,假设(否则可以交换),那么产生的边的贡献就是,分别计算点数和边数贡献,最终就可以求的答案了。